package demo1;

import java.util.Arrays;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    //捕获黑皇后需要的最小移动次数
    public int minMovesToCaptureTheQueen(int a, int b, int c, int d, int e, int f) {
        if (a == e && c != a) return 1;
        else if (b == f && d != b) return 1;
        if((a==c || b==d) && (a==e || b==f)) {
            int xMax = Math.max(a,e);
            int xMin = Math.min(a,e);
            int yMax = Math.max(b,f);
            int yMin = Math.min(b,f);
            if(a==c && d<yMax && d>yMin) return 2;
            else if(b==d && c<xMax && c>xMin) return 2;
            else return 1;
        }else{
            if (Math.abs(c - e) == Math.abs(d - f)) {
                int xMax = Math.max(c,e);
                int xMin = Math.min(c,e);
                int yMax = Math.max(d,f);
                int yMin = Math.min(d,f);
                if((a<xMax&&a>xMin) && (b<yMax && b>yMin)){
                    if(Math.abs(c - a) == Math.abs(d - b))
                        return 2;
                    else
                        return 1;
                }
                return 1;
            }
        }
        return 2;
    }
    //16 33 56

    //跳跃游戏 2
    //(On)
    public int jump(int[] nums) {
        int n = nums.length;
        int left = 0;
        int right = 0;
        int ret = 0;
        while(right>=n-1){
            int max = Integer.MIN_VALUE;
            for (int i = left; i <= right; i++) {
                max = Math.max(max,nums[i]+i);
            }
            right = max;
            left++;
            ret++;
        }
        return ret;
    }

    //(On^2)
    public int jump1(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = 0;
        for (int i = 1; i < n; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < i; j++) {
                if(nums[j]+j>=i) {
                    min = Math.min(min,dp[j]);
                }
            }
            dp[i] = min+1;
        }
        return dp[n-1];
    }

    //最优除法
    public String optimalDivision(int[] nums) {
        int size = 0;
        int key = nums[0];
        while(key>0){
            key/=10;
            size++;
        }
        StringBuilder stringBuilder = new StringBuilder();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            stringBuilder.append(nums[i]);
            if(i!=n-1) stringBuilder.append('/');
        }
        //if(n==2) stringBuilder.insert(1,'/');
        if(n>2){
            stringBuilder.insert(size+1,'(');
            stringBuilder.append(')');
        }
        return stringBuilder.toString();
    }

    //饼干分发
    public int findContentChildren(int[] g, int[] s) {
        int n = g.length;
        Arrays.sort(g);
        Arrays.sort(s);
        int ret = 0;
        int left = 0;
        for (int i = 0; i < n && left<s.length; left++) {
            if(s[left]>=g[i]){
                i++;
                ret++;
            }
        }
        return ret;
    }
}
